This application claims priority to U.S. Provisional Patent Application No. 60/330,755, filed Oct. 30, 2001, the entirety of which is incorporated herein by reference.
The present invention is directed to wireless networks, and particularly to optimizing throughput among multiple data rate communication devices in a wireless network.
In a wireless network, such as a wireless local area network (WLAN) that uses the IEEE 802.11x standard, communication devices that act as what is called in 802.11 parlance, stations (STAs), may use multiple data rates (e.g., 1, 2, 5.5, 11, . . . 54 Mbps) when communicating with a communication device that acts as what is called in 802.11 parlance, an access point (AP). The data rate assigned to a STA may be based on its proximity to the AP. For example, devices closer to the AP typically operate at faster data rates than devices further from the AP. Each frequency channel of 802.11 may be shared, via carrier sense multiple access/collision avoidance (CSMA/CA) procedures, by multiple STAs using various data rates. Each STA contends for use of the frequency channel and, on acquiring use of the channel, transmits a single MAC Service Data Unit (MSDU). While a given STA is transmitting an MSDU, no other STA is allowed to transmit on the channel. Additionally, the STA owns the channel until it has completely transmitted the MSDU. After transmitting an MSDU, the STA must contend again for use of the channel before sending another MSDU.
Currently, the 802.11 standard places no restrictions nor does it provide a recommendation for a data packet length, other than limiting the maximum MSDU size to no more than 2304 bytes. The required transmission time for a data packet of a given length is proportionally larger for low data rate users than for high data rate users. Consequently, the low data rate users may have a disproportionately higher percentage of medium access time than high data rate users, which limits throughput for the high data rate users.
To illustrate this, with reference to FIG. 1, an exemplary system 10 is shown having N STAs 120, where N=20. For example, there are ten 1 Mbps STAs and ten 54 Mbps STAs on a CSMA/CA WLAN. Each STA is attempting to upload a file to (or download a file from) a server via the WLAN AP 110. It is assumed each STA 120 uses a 2 KB MSDU size. To simplify the analysis, assume zero MAC overhead (i.e., MAC header, acknowledgements, DIFS, etc. take zero time). The following relations hold for this example.
Ts=Packet duration for “slow”users=2048*8/1=16,384 μs
Tf=Packet duration for “fast”users=2048*8/54=303 μs=Ts/54
Throughput per slow user: 1 Mbps*54/55/10≅100 kbps
Throughput per fast user: 54 Mbps*1/55/10≅100 kbps
Average throughput per user: 100 kbps
As this example shows, the slow users take much longer to transmit their packets than the fast users, effectively negating the benefit of the higher data rate for the fast users. More specifically, the slow users spend 54 times more time on the medium than fast users in this scenario (since it takes them 54 times longer to transmit or receive a 2 KB packet) assuming that all users contend for the medium using CSMA/CA procedures for the transmission of each packet. Slow users own the medium 54/55=98% of the time, whereas fast users own the medium 1/55=2% of the time. The results would be the same if a MSDU size of 500 bytes, for example, were used.
To generalize, assume there are Ns low data rate users and Ns high data rate users of a CSMA/CA WLAN. The following relations are given:
Ts=M*Tf=Packet duration for a slow users
Tf=Packet duration for fast users
M=ratio of highest data rate to lowest data rate for the users on the network (Rf/Rs)
Rf=Fastest user data rate
Rs=Slowest user data rate
Throughput for slow data rate user=Rs*Ts/(Ns*Ts+Nf*Tf)=Rs*M/(Ns*M+Nf)≈Rs/Ns (since Ns*M usually>>Nf)
Throughput for fast data rate=Rf*Tf/(Ns*Ts+Nf*Tf)=Rf/(Ns*M+Nf)≈Rs/Ns (again, assuming Ns*M>>Nf).
Average throughput per user≈Rs/(Ns).
In summary, all STAs experience substantially the same throughput equal to the slowest user's data rate divided by the number of slow users. The high data rate users do not realize the benefit of their faster data rates because throughput is limited by the slowest user data rate.
In more extreme cases, the overall performance of a wireless network can collapse as additional users, particularly slow users, access the network. FIG. 2 illustrates a plot of access time of a user versus percent utilization of the network. Even at zero percent utilization, there is a minimum access time to for a user to obtain access to the network. As more users access the network, the access time increases, and at some point (approximately 50% utilization), the access time increases exponentially. FIG. 2 illustrates that throughput for all users on the network can become unacceptable as the network utilization increases, particularly with slow users, and at some the network may collapse completely. Network administrators struggle with techniques to prevent network collapse.
Solutions are needed to contend with the foregoing challenges in maintaining stability of a wireless network with multiple data rate users.